//
// Created by madison on 2022/6/21.
//

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

class Solution {
public:
    /**
     * 方法一：排序
     * @param nums
     * @return
     */
    bool containsDuplicate(vector<int> &nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for (int i = 0; i < n - 1; ++i) {
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        return false;
    }

    /**
     * 方法二：哈希表
     * @param nums
     * @return
     */
    bool containsDuplicate1(vector<int> &nums) {
        unordered_set<int> s;
        for (int x: nums) {
            if (s.find(x) != s.end()) {
                return true;
            }
            s.insert(x);
        }
        return false;
    }
};

int main() {
    Solution solution;
    vector<int> nums = {1, 1, 1, 3, 3, 4, 3, 2, 4, 2};
    cout << solution.containsDuplicate1(nums) << endl;
    return 0;
}